/*********************************************************************************************************
 *  ------------------------------------------------------------------------------------------------------
 *  file description
 *  ------------------------------------------------------------------------------------------------------
 *         \file  algorithm.c
 *        \brief  This is a general-purpose C language algorithm module
 *       \author  Lamdonn
 *        \email  Lamdonn@163.com
 *      \version  1.0.0
 *      \license  GPL2
 *    \copyright  Copyright (C) 2023 Lamdonn.
 ********************************************************************************************************/
#include "vlib.h"
#include <string.h>

/* special swap function declaration */
extern void list_algorithm_swap(vobject_t object, void *node0, void *node1);
extern void set_algorithm_swap(vobject_t object, void *node0, void *node1);
extern void map_algorithm_swap(vobject_t object, void *node0, void *node1);
static void universal_swap(vobject_t object, void *node0, void *node1);

/* function operation set type define */
typedef struct 
{
    void (*swap)(vobject_t object, void *node0, void *node1);   /* fast way for containers to swap data */
} algorithm_ops;

/* algorithm operation function list definition */
static algorithm_ops ops[9] = {
/*  swap                    */
    {NULL                   }, /* unknow */
    {universal_swap         }, /* str */
    {universal_swap         }, /* vector */
    {universal_swap         }, /* queue */
    {universal_swap         }, /* stack */
    {universal_swap         }, /* deque */
    {list_algorithm_swap    }, /* list */
    {set_algorithm_swap     }, /* set */
    {map_algorithm_swap     }, /* map */
};

/* universal swap function */
static void universal_swap(vobject_t object, void *node0, void *node1)
{
    int i = 0;
    char temp;
    for (i = 0; i < object->dsize; i++)
    {
        temp = ((char *)node0)[i];
        ((char *)node0)[i] = ((char *)node1)[i];
        ((char *)node1)[i] = temp;
    }
}

int alg_count(iterator begin, iterator end, void *data)
{
    iterator it;
    int count = 0;

    /* check whether the incoming parameter is valid */
    if (!it_valid(begin) || !it_valid(end)) return 0;
    if (!data) return 0;

    /* whether the begin iterator and the end iterator belong to the same container */
    if (begin.object != end.object && begin.object->base != end.object->base) return 0; // the base of an array is the same and is considered the same container
    
    /* check the begin and end iterator positions */
    if (begin.pos > end.pos) return 0;

    /* check whether the type is valid */
    if (vtype(begin.object) == VTYPE_UNKNOW) return 0;

    /* ergodic statistics */
    for (it = begin; it.pos <= end.pos; it_move(it, 1))
    {
        if (!memcmp(data, it_value(it), it.object->dsize)) count++;
    }

    return count;
}

int alg_count_if(iterator begin, iterator end, int (*pred)(void *data))
{
    iterator it;
    int count = 0;

    /* check whether the incoming parameter is valid */
    if (!it_valid(begin) || !it_valid(end)) return 0;
    if (!pred) return 0;

    /* whether the begin iterator and the end iterator belong to the same container */
    if (begin.object != end.object && begin.object->base != end.object->base) return 0;

    /* check the begin and end iterator positions */
    if (begin.pos > end.pos) return 0;

    /* check whether the type is valid */
    if (vtype(begin.object) == VTYPE_UNKNOW) return 0;

    /* ergodic statistics */
    for (it = begin; it.pos <= end.pos; it_move(it, 1))
    {
        if (pred(it_value(it))) count++;
    }

    return count;
}

iterator alg_find(iterator begin, iterator end, void *data)
{
    iterator it;

    /* check whether the incoming parameter is valid */
    if (!it_valid(begin) || !it_valid(end)) goto FAIL;
    if (!data) goto FAIL;

    /* whether the begin iterator and the end iterator belong to the same container */
    if (begin.object != end.object && begin.object->base != end.object->base) goto FAIL;

    /* check whether the type is valid */
    if (vtype(begin.object) == VTYPE_UNKNOW) goto FAIL;

    /* find forward */
    if (begin.pos < end.pos)
    {
        for (it = begin; it.pos <= end.pos; it_move(it, 1))
        {
            if (!memcmp(data, it_value(it), it.object->dsize)) return it;
        }
    }
    /* find reverse */
    else 
    {
        for (it = begin; it.pos >= end.pos; it_move(it, -1))
        {
            if (!memcmp(data, it_value(it), it.object->dsize)) return it;
        }
    }

FAIL:
    it.object = NULL;
    it.node = NULL;
    it.pos = 0;

    return it;
}

iterator alg_find_if(iterator begin, iterator end, int (*pred)(void *data))
{
    iterator it;

    /* check whether the incoming parameter is valid */
    if (!it_valid(begin) || !it_valid(end)) goto FAIL;
    if (!pred) goto FAIL;

    /* whether the begin iterator and the end iterator belong to the same container */
    if (begin.object != end.object && begin.object->base != end.object->base) goto FAIL;

    /* check whether the type is valid */
    if (vtype(begin.object) == VTYPE_UNKNOW) goto FAIL;

    /* find forward */
    if (begin.pos < end.pos)
    {
        for (it = begin; it.pos <= end.pos; it_move(it, 1))
        {
            if (pred(it_value(it))) return it;
        }
    }
    /* find reverse */
    else 
    {
        for (it = begin; it.pos >= end.pos; it_move(it, -1))
        {
            if (pred(it_value(it))) return it;
        }
    }

FAIL:
    it.object = NULL;
    it.node = NULL;
    it.pos = 0;

    return it;
}

void alg_for_each(iterator begin, iterator end, void (*func)(iterator it))
{
    iterator it;

    /* check whether the incoming parameter is valid */
    if (!it_valid(begin) || !it_valid(end)) return;
    if (!func) return;

    /* whether the begin iterator and the end iterator belong to the same container */
    if (begin.object != end.object && begin.object->base != end.object->base) return;

    /* check whether the type is valid */
    if (vtype(begin.object) == VTYPE_UNKNOW) return;

    /* ergodic forward */
    if (begin.pos < end.pos)
    {
        for (it = begin; it.pos <= end.pos; it_move(it, 1))
        {
            func(it);
        }
    }
    /* ergodic reverse */
    else 
    {
        for (it = begin; it.pos >= end.pos; it_move(it, -1))
        {
            func(it);
        }
    }
}

int alg_reverse(iterator begin, iterator end)
{
    iterator it;
    int type = 0;
    
    /* check whether the incoming parameter is valid */
    if (!it_valid(begin) || !it_valid(end)) return 0;

    /* whether the begin iterator and the end iterator belong to the same container */
    if (begin.object != end.object && begin.object->base != end.object->base) return 0;

    /* check whether the type is valid */
    type = vtype(begin.object);
    if (type == VTYPE_UNKNOW) return 0;

    /* if the begin and end positions are opposite, adjust the positions */
    if (begin.pos > end.pos) 
    {
        it = begin;
        begin = end;
        end = it;
    }

    /* ergodic swap */
    while (end.pos - begin.pos > 0)
    {
        ops[type].swap(begin.object, begin.node, end.node);
        it_move(begin, 1);
        it_move(end, -1);
    }

    return 1;
}

int alg_sort_bubble(iterator begin, iterator end, int (*rule)(void *front, void *back))
{
    iterator i, j;
    int type;

    /* check whether the incoming parameter is valid */
    if (!it_valid(begin) || !it_valid(end)) return 0;
    if (!rule) return 0;

    /* whether the begin iterator and the end iterator belong to the same container */
    if (begin.object != end.object && begin.object->base != end.object->base) return 0;

    /* check the begin and end iterator positions */
    if (begin.pos > end.pos) return 0;

    /* check whether the type is valid */
    type = vtype(begin.object);
    if (type == VTYPE_UNKNOW) return 0;
    
    for (i = begin; i.pos <= end.pos; it_move(i, 1))
    {
        for (j = i; j.pos <= end.pos; it_move(j, 1))
        {
            if (rule(it_value(i), it_value(j)) == -1)
            {
                ops[type].swap(i.object, i.node, j.node);
            }
        }
    }

    return 1;
}

int alg_sort_select(iterator begin, iterator end, int (*rule)(void *front, void *back))
{
    iterator i, j, temp;
    int type;

    /* check whether the incoming parameter is valid */
    if (!it_valid(begin) || !it_valid(end)) return 0;
    if (!rule) return 0;

    /* whether the begin iterator and the end iterator belong to the same container */
    if (begin.object != end.object && begin.object->base != end.object->base) return 0;

    /* check the begin and end iterator positions */
    if (begin.pos > end.pos) return 0;

    /* check whether the type is valid */
    type = vtype(begin.object);
    if (type == VTYPE_UNKNOW) return 0;

    for (i = begin; i.pos <= end.pos; it_move(i, 1))
    {
        temp = i;
        for (j = i, it_move(j, 1); j.pos <= end.pos; it_move(j, 1))
        {
            if (rule(it_value(temp), it_value(j)) == -1)
            {
                temp = j;
            }        
        }
        if (temp.pos != i.pos)
        {
            ops[type].swap(temp.object, temp.node, i.node);
        }
    }

    return 1;
}

int alg_sort_insert(iterator begin, iterator end, int (*rule)(void *front, void *back))
{
    iterator i, j, t, p;
    int type;

    /* check whether the incoming parameter is valid */
    if (!it_valid(begin) || !it_valid(end)) return 0;
    if (!rule) return 0;

    /* whether the begin iterator and the end iterator belong to the same container */
    if (begin.object != end.object && begin.object->base != end.object->base) return 0;

    /* check the begin and end iterator positions */
    if (begin.pos > end.pos) return 0;

    /* check whether the type is valid */
    type = vtype(begin.object);
    if (type == VTYPE_UNKNOW) return 0;
    
    for (i = begin, it_move(i, 1); i.pos < end.pos + 1; it_move(i, 1))
    {
        t = i, it_move(t, -1);
        if (rule(it_value(t), it_value(i)) == -1)
        {
            for (j = t; j.pos >= begin.pos; it_move(j, -1))
            {
                p = j, it_move(p, 1);
                if (rule(it_value(j), it_value(p)) == -1)
                {
                    ops[type].swap(j.object, j.node, p.node);
                }
                else 
                {
                    break;
                }
            }
        }
    }

    return 1;
}

int alg_sort_shell(iterator begin, iterator end, int (*rule)(void *front, void *back))
{
    iterator i, j, k, t, p;
    int increasement = end.pos + 1 - begin.pos;
    int type;

    /* check whether the incoming parameter is valid */
    if (!it_valid(begin) || !it_valid(end)) return 0;
    if (!rule) return 0;

    /* whether the begin iterator and the end iterator belong to the same container */
    if (begin.object != end.object && begin.object->base != end.object->base) return 0;

    /* check the begin and end iterator positions */
    if (begin.pos > end.pos) return 0;

    /* check whether the type is valid */
    type = vtype(begin.object);
    if (type == VTYPE_UNKNOW) return 0;

    do
    {
        /* Determine the increment of the grouping */
        increasement = increasement / 3 + 1;
        for (i = begin; i.pos < increasement + begin.pos; it_move(i, 1))
        {
            for (j = i, t = j, it_move(j, increasement); j.pos <= end.pos; it_move(j, increasement))
            {
                if (rule(it_value(t), it_value(j)) == -1)
                {
                    for (k = j, p = k, it_move(k, -increasement); k.pos >= begin.pos; it_move(k, -increasement))
                    {
                        if (rule(it_value(k), it_value(p)) == -1)
                        {
                            ops[type].swap(p.object, p.node, k.node);
                        }
                        else 
                        {
                            break;
                        }
                        p = k;
                    }
                }
                t = j;
            }
        }
    } while (increasement > 1);

    return 1;
}

static int sort_quick(iterator begin, iterator end, int type, int (*rule)(void *front, void *back))
{
    iterator i = begin, j = end, t = begin;

    /* check the begin and end iterator positions */
    if (i.pos >= j.pos) return 0;

    while (i.pos != j.pos)
    {
        /* Find numbers that do not conform to the sorting rules from right to left */
        while (rule(it_value(j), it_value(t)) != 1 && j.pos > i.pos) it_move(j, -1);

        /* Find numbers that do not violate the ordering rules from left to right */
        while (rule(it_value(i), it_value(t)) != -1 && j.pos > i.pos) it_move(i, 1);

        if (j.pos > i.pos) ops[type].swap(i.object, i.node, j.node);
    }
    ops[type].swap(i.object, i.node, t.node);

    /* Recursively sort subsequences */
    sort_quick(begin, i, type, rule);
    it_move(i, 1);
    sort_quick(i, end, type, rule);

    return 1;
}

int alg_sort_quick(iterator begin, iterator end, int (*rule)(void *front, void *back))
{
    iterator i = begin, j = end, t = begin;
    int type;

    /* check whether the incoming parameter is valid */
    if (!it_valid(begin) || !it_valid(end)) return 0;
    if (!rule) return 0;

    /* whether the begin iterator and the end iterator belong to the same container */
    if (begin.object != end.object && begin.object->base != end.object->base) return 0;

    /* check the begin and end iterator positions */
    if (begin.pos > end.pos) return 0;

    /* check whether the type is valid */
    type = vtype(begin.object);
    if (type == VTYPE_UNKNOW) return 0;
    
    return sort_quick(begin, end, type, rule);
}

static void heap_adjust(iterator begin, iterator i, iterator end, int type, int (*rule)(void *front, void *back))
{
    iterator parent = i, lchild, rchild;
    
    lchild = begin;
    it_move(lchild, (i.pos - begin.pos) * 2 + 1);
    rchild = lchild;
    it_move(rchild, 1);

    if (lchild.pos < end.pos + 1 && rule(it_value(lchild), it_value(parent)) == -1)
    {
        parent = lchild;
    }

    if (rchild.pos < end.pos + 1 && rule(it_value(rchild), it_value(parent)) == -1)
    {
        parent = rchild;
    }

    /* If the value at i is smaller than the value of its left and right child nodes, swap it with the parent value */
    if (parent.pos != i.pos)
    {
        ops[type].swap(i.object, i.node, parent.node);
        /* Recursion */
        heap_adjust(begin, parent, end, type, rule);
    }
}

int alg_sort_heap(iterator begin, iterator end, int (*rule)(void *front, void *back))
{    
    iterator i;
    int length = end.pos - begin.pos + 1;
    int type;

    /* check whether the incoming parameter is valid */
    if (!it_valid(begin) || !it_valid(end)) return 0;
    if (!rule) return 0;

    /* whether the begin iterator and the end iterator belong to the same container */
    if (begin.object != end.object && begin.object->base != end.object->base) return 0;

    /* check the begin and end iterator positions */
    if (begin.pos > end.pos) return 0;

    /* check whether the type is valid */
    type = vtype(begin.object);
    if (type == VTYPE_UNKNOW) return 0;

    /* Init heap, (length / 2 - 1 + begin) is the sequence number of the last non-leaf node in the binary tree*/
    for (i = begin, it_move(i, length / 2 - 1); i.pos >= begin.pos; it_move(i, -1))
    {
        heap_adjust(begin, i, end, type, rule);
    }
    /* Swap the top and last elements of the heap */
    for (i = end; i.pos >= begin.pos; )
    {
        ops[type].swap(begin.object, begin.node, i.node);
        it_move(i, -1);
        heap_adjust(begin, begin, i, type, rule);
    }

    return 1;
}

int alg_sort(iterator begin, iterator end, int (*rule)(void *front, void *back))
{
    iterator i = begin, j = end, t = begin;
    int type;

    /* check whether the incoming parameter is valid */
    if (!it_valid(begin) || !it_valid(end)) return 0;
    if (!rule) return 0;

    /* whether the begin iterator and the end iterator belong to the same container */
    if (begin.object != end.object && begin.object->base != end.object->base) return 0;

    /* check the begin and end iterator positions */
    if (begin.pos > end.pos) return 0;

    /* check whether the type is valid */
    type = vtype(begin.object);
    if (type == VTYPE_UNKNOW) return 0;
    
    while (i.pos != j.pos)
    {
        /* Find numbers that do not conform to the sorting rules from right to left */
        while (rule(it_value(j), it_value(t)) != 1 && j.pos > i.pos) it_move(j, -1);

        /* Find numbers that do not violate the ordering rules from left to right */
        while (rule(it_value(i), it_value(t)) != -1 && j.pos > i.pos) it_move(i, 1);

        if (j.pos > i.pos) ops[type].swap(i.object, i.node, j.node);
    }
    ops[type].swap(i.object, i.node, t.node);

    if (i.pos - begin.pos < 16) alg_sort_insert(begin, i, rule);
    else alg_sort(begin, i, rule);
    it_move(i, 1);
    if (end.pos - i.pos < 16) alg_sort_insert(i, end, rule);
    else alg_sort(i, end, rule);

    return 1;
}

int alg_fill(iterator begin, iterator end, void *data)
{
    iterator it;

    /* check whether the incoming parameter is valid */
    if (!it_valid(begin) || !it_valid(end)) return 0;

    /* whether the begin iterator and the end iterator belong to the same container */
    if (begin.object != end.object && begin.object->base != end.object->base) return 0;

    /* check the begin and end iterator positions */
    if (begin.pos > end.pos) return 0;

    /* check whether the type is valid */
    if (vtype(begin.object) == VTYPE_UNKNOW) return 0;

    /* iterate to fill */
    for (it = begin; it.pos <= end.pos; it_move(it, 1))
    {
        memcpy(it_value(it), data, it.object->dsize);
    }

    return it.pos - begin.pos;
}

int alg_fill_n(iterator begin, int n, void *data)
{
    iterator it;

    /* check whether the incoming parameter is valid */
    if (!it_valid(begin)) return 0;
    if (n <= 0) return 0;
    if (!data) return 0;

    /* check whether the type is valid */
    if (vtype(begin.object) == VTYPE_UNKNOW) return 0;

    /* iterate to fill */
    for (it = begin; n > 0 && it.pos < it.object->size; it_move(it, 1), n--)
    {
        memcpy(it_value(it), data, it.object->dsize);
    }

    return it.pos - begin.pos;
}

int alg_copy(iterator begin, iterator end, iterator dest)
{
    iterator it;

    /* check whether the incoming parameter is valid */
    if (!it_valid(begin) || !it_valid(end) || !it_valid(dest)) return 0;

    /* whether the begin iterator and the end iterator belong to the same container */
    if (begin.object != end.object && begin.object->base != end.object->base) return 0;

    /* check the begin and end iterator positions */
    if (begin.pos > end.pos) return 0;

    /* check whether the type is valid */
    if (vtype(begin.object) == VTYPE_UNKNOW) return 0;
    if (vtype(dest.object) == VTYPE_UNKNOW) return 0;

    /* check if the data size stored in two containers is consistent to prevent cross boundary operations */
    if (begin.object->dsize != dest.object->dsize) return 0;

    /* iterate to copy */
    for (it = begin; it_valid(dest) && it.pos <= end.pos; it_move(it, 1), it_move(dest, 1))
    {
        memcpy(it_value(dest), it_value(it), it.object->dsize);
    }

    return it.pos - begin.pos;
}

int alg_unique(iterator begin, iterator end, int (*cmp)(void *ref, void *data))
{
    iterator i = begin, o = begin;

    /* check whether the incoming parameter is valid */
    if (!it_valid(begin) || !it_valid(end)) return 0;

    /* whether the begin iterator and the end iterator belong to the same container */
    if (begin.object != end.object && begin.object->base != end.object->base) return 0;

    /* check the begin and end iterator positions */
    if (begin.pos > end.pos) return 0;

    /* check whether the type is valid */
    if (vtype(begin.object) == VTYPE_UNKNOW) return 0;

    /* using the default comparison method to compare address content */
    if (!cmp)
    {
        for (it_move(i, 1); i.pos <= end.pos; it_move(i, 1))
        {
            if (memcmp(it_value(o), it_value(i), o.object->dsize))
            {
                it_move(o, 1);
                memcpy(it_value(o), it_value(i), o.object->dsize);
            }
        }
    }
    /* using the specified comparison method */
    else 
    {
        for (it_move(i, 1); i.pos <= end.pos; it_move(i, 1))
        {
            if (cmp(it_value(o), it_value(i)))
            {
                it_move(o, 1);
                memcpy(it_value(o), it_value(i), o.object->dsize);
            }
        }
    }

    return i.pos - o.pos - 1;
}

int alg_replace(iterator begin, iterator end, void *old, void *new)
{
    iterator it;
    int count = 0;

    /* check whether the incoming parameter is valid */
    if (!it_valid(begin) || !it_valid(end)) return 0;

    /* whether the begin iterator and the end iterator belong to the same container */
    if (begin.object != end.object && begin.object->base != end.object->base) return 0;

    /* check the begin and end iterator positions */
    if (begin.pos > end.pos) return 0;

    /* check whether the type is valid */
    if (vtype(begin.object) == VTYPE_UNKNOW) return 0;

    /* iterate to replace */
    for (it = begin; it.pos <= end.pos; it_move(it, 1))
    {
        if (!memcmp(it_value(it), old, it.object->dsize))
        {
            memcpy(it_value(it), new, it.object->dsize);
            count++;
        }
    }

    return count;
}

int alg_replace_if(iterator begin, iterator end, int (*pred)(void *data), void *new)
{
    iterator it;
    int count = 0;

    /* check whether the incoming parameter is valid */
    if (!it_valid(begin) || !it_valid(end)) return 0;

    /* whether the begin iterator and the end iterator belong to the same container */
    if (begin.object != end.object && begin.object->base != end.object->base) return 0;

    /* check the begin and end iterator positions */
    if (begin.pos > end.pos) return 0;

    /* check whether the type is valid */
    if (vtype(begin.object) == VTYPE_UNKNOW) return 0;

    /* iterate to replace */
    for (it = begin; it.pos <= end.pos; it_move(it, 1))
    {
        if (pred(it_value(it)))
        {
            memcpy(it_value(it), new, it.object->dsize);
            count++;
        }
    }

    return count;
}

int alg_remove(iterator begin, iterator end, void *data)
{
    iterator i = begin, o = begin;
    int count = 0;

    /* check whether the incoming parameter is valid */
    if (!it_valid(begin) || !it_valid(end)) return 0;

    /* whether the begin iterator and the end iterator belong to the same container */
    if (begin.object != end.object && begin.object->base != end.object->base) return 0;

    /* check the begin and end iterator positions */
    if (begin.pos > end.pos) return 0;

    /* check whether the type is valid */
    if (vtype(begin.object) == VTYPE_UNKNOW) return 0;

    /* iterate to replace */
    for (; i.pos <= end.pos; it_move(i, 1))
    {
        /* skip encountered matching data */
        if (!memcmp(it_value(i), data, i.object->dsize))
        {
            count++;
            continue;
        }

        /* if the location is different, use the data from iterator 'i' to cover the data from iterator 'o' */
        if (o.pos != i.pos)
        {
            memcpy(it_value(o), it_value(i), o.object->dsize);
        }

        /* after the 'o' iterator receives the data, it moves back */
        it_move(o, 1);
    }

    return count;
}

int alg_remove_if(iterator begin, iterator end, int (*pred)(void *data))
{
    iterator i = begin, o = begin;
    int count = 0;

    /* check whether the incoming parameter is valid */
    if (!it_valid(begin) || !it_valid(end)) return 0;

    /* whether the begin iterator and the end iterator belong to the same container */
    if (begin.object != end.object && begin.object->base != end.object->base) return 0;

    /* check the begin and end iterator positions */
    if (begin.pos > end.pos) return 0;

    /* check whether the type is valid */
    if (vtype(begin.object) == VTYPE_UNKNOW) return 0;

    /* iterate to replace */
    for (; i.pos <= end.pos; it_move(i, 1))
    {
        /* skip encountered matching data */
        if (pred(it_value(i)))
        {
            count++;
            continue;
        }

        /* if the location is different, use the data from iterator 'i' to cover the data from iterator 'o' */
        if (o.pos != i.pos)
        {
            memcpy(it_value(o), it_value(i), o.object->dsize);
        }

        /* after the 'o' iterator receives the data, it moves back */
        it_move(o, 1);
    }

    return count;
}

iterator alg_search(iterator begin1, iterator end1, iterator begin2, iterator end2)
{
    iterator it, i, j;

    /* check whether the incoming parameter is valid */
    if (!it_valid(begin1) || !it_valid(end1)) goto FAIL;
    if (!it_valid(begin2) || !it_valid(end2)) goto FAIL;

    /* whether the begin iterator and the end iterator belong to the same container */
    if (begin1.object != end1.object && begin1.object->base != end1.object->base) goto FAIL;
    if (begin2.object != end2.object && begin2.object->base != end2.object->base) goto FAIL;

    /* check the begin and end iterator positions */
    if (begin1.pos > begin1.pos) goto FAIL;
    if (begin2.pos > begin2.pos) goto FAIL;

    /* interval 1 is smaller than interval 2 and directly fail */
    if (end1.pos - begin1.pos < end2.pos - begin2.pos) goto FAIL;

    /* check whether the type is valid */
    if (vtype(begin1.object) == VTYPE_UNKNOW) goto FAIL;
    if (vtype(begin2.object) == VTYPE_UNKNOW) goto FAIL;

    /* iterate to search */
    for (it = begin1; it.pos <= end1.pos - (end2.pos - begin2.pos); it_move(it, 1))
    {
        /* it points to a value that matches the first value in interval 2 and continues to match the remaining values */
        if (!memcmp(it_value(it), it_value(begin2), it.object->dsize))
        {
            /* move to the next position */
            i = it;
            it_move(i, 1);
            j = begin2;
            it_move(j, 1);

            /* match the remaining values */
            for (; i.pos < it.pos + (end2.pos - begin2.pos) + 1; it_move(i, 1), it_move(j, 1))
            {
                if (memcmp(it_value(i), it_value(j), i.object->dsize)) break;
            }

            /* the loop is over, which means there are all match */
            if (i.pos == it.pos + (end2.pos - begin2.pos) + 1) return it;
        }
    }
FAIL:
    it.object = NULL;
    it.node = NULL;
    it.pos = 0;
    return it;
}

/* TODO: 
    transform
    max / min
    max_element / min_element
    rotate
    random_shuffle
    search_n
    equal
    includes
    mismatch
    swap
    merge
*/